//1.O(nlogn) 排序耗时
/*
遍历每个字符串
对它进行排序（如 "eat" → "aet", "tea" → "aet")
用排序后的字符串作为哈希表的键
将原始字符串作为值加入到这个键对应的组里
*/
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        unordered_map<string, vector<string>> hashmap;

        for (string& str : strs) {
            string key = str;
            sort(key.begin(), key.end());
            hashmap[key].push_back(str);
        }

        for(auto& [key, val]: hashmap) {
            ret.push_back(val);
        }
        return ret;
    }
};

//2.异位词除了排序相同，它们的每个字母出现次数也相同。 与其排序，不如统计它的 26 个字母出现频率，用这个频率作为“签名”。
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> map;
        for(string str:strs) {
            int counts[26] = {0};
            for(char c:str) {
                counts[c-'a']++;
            }
            string key = "";
            for(int i = 0;i<26;++i) {
                if(counts[i]!=0) {
                    key.push_back(i+'a');
                    key.push_back('0'+counts[i]); //'0'-->48, 48+100没有超出char的范围
                }
            }
            map[key].push_back(str);
        }
        vector<vector<string>> res;
        for(auto& [key,val]:map) {
            res.push_back(val);
        }
        return res;
    }
};



